package com.leetcode;

//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//
// 算法的时间复杂度应该为 O(log (m+n)) 。
//
//
//
// 示例 1：
//
//
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
//
//
// 示例 2：
//
//
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
//
//
public class No4 {
    /**
     * 如果长度和为偶数, 则需要找到中间两个数
     * 否则只需要一个数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        int left = -1, right = -1;
        int start1 = 0, start2 = 0;
        for (int i = 0; i <= len / 2; i++) {
            left = right;
            if (start1 < nums1.length && (start2 >= nums2.length || nums1[start1] <= nums2[start2])) {
                right = nums1[start1];
                start1++;
            } else {
                right = nums2[start2];
                start2++;
            }
        }
        // 偶数
        if ((len & 1) == 0) {
            return (left + right) / 2.0;
        } else {
            return left;
        }
    }
}
